package com.zklh.leetcode.structure.uf;

/**
 * @author ：tong nan
 * @date ：Created in 2021/6/3 17:54
 * @description ：并查集算法实现
 * @modifiedBy ：
 */
public class UnionFindStructureV3 implements UnionFindStructure{
    private int[] parent;
    private int count;
    private int[] size;

    public UnionFindStructureV3(int n) {
        parent = new int[n];
        size = new int[n];
        for (int i = 0; i < n; i++) {
            parent[i] = i;
            size[i] =1;
        }
        count = n;
    }

    /**
     * 连通两个结点
     * @param p
     * @param q
     */
    public void union(int p, int q) {
        int rootP = find(p);
        int rootQ = find(q);
        if (rootP == rootQ) {
            return;
        }
        // 让小的树挂在大的树下
        if (size[rootP] >= size[rootQ]) {
            parent[rootQ] = rootP;
            size[rootP] += 1;
        } else {
            parent[rootP] = rootQ;
            size[rootQ] +=1;
        }
        count--;
    }

    /**
     * 寻找x的连接的根节点
     * @param x
     * @return
     */
    private int find(int x) {
        while (parent[x] != x) {
            parent[x] = parent[parent[x]];
            x = parent[x];
        }
        return x;
    }


    public boolean connected(int p, int q) {
        int rootP = find(p);
        int rootQ = find(q);
        return rootP == rootQ;
    }

    public int count(){
        return count;
    }

    public static void main(String[] args) {
        UnionFindStructureV3 structure = new UnionFindStructureV3(10);
        structure.union(0,1);
        structure.union(1,2);
        structure.union(3,4);
        structure.union(1,3);
        boolean connected = structure.connected(0, 2);
        boolean connected1 = structure.connected(2, 3);
        boolean connected2 = structure.connected(4, 6);
        int count = structure.count();
    }
}
